#include "myGraph.h"
#include <iostream>
#include <sstream>
#include <string>
#include <queue>

using namespace std;

EdgeNode::EdgeNode(){
	dest = -1;
	link = NULL;
}

EdgeNode::EdgeNode(int dest, EdgeNode* link){
	this->dest = dest;
	this->link = link;
}

EdgeNode::~EdgeNode(){

}

int EdgeNode::getDest(){
	return dest;
}

EdgeNode* EdgeNode::getNext(){
	return link;
}

void EdgeNode::setDest(int dest){
	this->dest = dest;
}

void EdgeNode::setNext(EdgeNode* link){
	this->link = link;
}

VertexNode::VertexNode(){
	data = 0;
	firstEdge = NULL;
}

VertexNode::VertexNode(char data, EdgeNode* firstEdge){
	this->data = data;
	this->firstEdge = firstEdge;
}

VertexNode::~VertexNode(){

}

char VertexNode::getData(){
	return data;
}

EdgeNode* VertexNode::getFirstEdge(){
	return firstEdge;
}

void VertexNode::setData(char data){
	this->data = data;
}

void VertexNode::setFirstEdge(EdgeNode* firstEdge){
	firstEdge->setNext(this->firstEdge);
	this->firstEdge = firstEdge;
}

MyGraph::MyGraph(){
	nodeNum = 0;
	edgeNum = 0;
	VexList = NULL;
}

MyGraph::MyGraph(int nodeNum, int edgeNum, char* nodeList, int* edgeStartList, int* edgeEndList) {
	this->nodeNum = nodeNum;
	this->edgeNum = edgeNum;
	VexList = new VertexNode[nodeNum];
	for (int i = 0; i < nodeNum; i++) VexList[i].setData(nodeList[i]);
	for (int i = 0; i < edgeNum; i++) {
		EdgeNode* edge1 = new EdgeNode(edgeEndList[i], NULL);
		VexList[edgeStartList[i]].setFirstEdge(edge1);
		EdgeNode* edge2 = new EdgeNode(edgeStartList[i], NULL);
		VexList[edgeEndList[i]].setFirstEdge(edge2);
	}
}

MyGraph::~MyGraph(){
	for (int i = 0; i < nodeNum; i++) {
		EdgeNode* p = VexList[i].getFirstEdge();
		EdgeNode* q;
		while (p != NULL) {
			q = p;
			p = p->getNext();
			delete q;
		}
	}
	delete[] VexList;
}

int MyGraph::getNodeNum(){
	return nodeNum;
}

int MyGraph::getEdgeNum(){
	return edgeNum;
}

string MyGraph::printGraph(){
	string s;
	for (int i = 0; i < nodeNum; i++) {
		s.append(1, VexList[i].getData());
		s.append(1, ':');
		EdgeNode* p = VexList[i].getFirstEdge();
		while (p!=NULL) {
			s.append(1, ' ');
			s.append(1, VexList[p->getDest()].getData());
			p = p->getNext();
		}
		if (i != nodeNum - 1) s.append(1, '\n');
	}
	return s;
}

int MyGraph::getFirstNeighbor(int v, int* visited){
	return 0;
}

int MyGraph::getNextNeighbor(int v, int w, int* visited){
	return 0;
}

void MyGraph::DFS(int v, int* visited, string& result){
	visited[v] = 1;
	result.append(1, VexList[v].getData());
	result.append(1, ' ');
	EdgeNode* p = VexList[v].getFirstEdge();
	while (p != NULL) {
		if(!visited[p->getDest()]) DFS(p->getDest(), visited, result);
		p = p->getNext();
	}
}

string MyGraph::graph_DFS_Traverse(){
	string s;
	int* visited = new int[nodeNum];
	for (int i = 0; i < nodeNum; i++) visited[i] = 0;
	for (int i = 0; i < nodeNum; i++) if (!visited[i]) DFS(i,visited, s);
	delete[] visited;
	return s;
}

void MyGraph::BFS(int v, int* visited, string& result){

}

string MyGraph::graph_BFS_Traverse(){
	string s;
	bool* visited = new bool[nodeNum];
	for (int i = 1; i < nodeNum; i++) visited[i] = false;
	queue<int> q;
	q.push(0);
	visited[0] = true;
	while (!q.empty()) {
		EdgeNode* p = VexList[q.front()].getFirstEdge();
		while (p != NULL) {
			if (!visited[p->getDest()]) {
				q.push(p->getDest());
				visited[p->getDest()] = true;
			}
			p = p->getNext();
		}
		s.append(1, VexList[q.front()].getData());
		s.append(1, ' ');
		q.pop();
	}
	delete[] visited;
	return s;
}
